package linkedList;

public class LinkedPractice_3_14 {
    static class ListNode{
        private int val;
        private ListNode next = null;

        public ListNode(){
            this(0);
        }
        public ListNode(int val) {
            this.val = val;
        }
    }
    /*
    203. 移除链表元素
    给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有
    满足 Node.val == val 的节点，并返回 新的头节点 。
    */
    public ListNode removeElements(ListNode head, int val) {
        //空链表，不用删除，返回空
        if(head == null){
            return null;
        }
        ListNode prev = head;
        ListNode cur = head.next;
        //非空链表，从头结点后一结点开始删除元素等于val的结点
        while(cur != null){
            if(cur.val == val){
                //找到值等于val的结点直接删除
                cur = cur.next;
                prev.next = cur;
                continue;
            }
            //未找到值等于val的结点，更新prev、cur
            prev = cur;
            cur = cur.next;
        }
        //判断头结点的值是否等于val，等于删除头结点
        if(head.val == val){
            head = head.next;
        }
        //返回删除后的链表
        return head;
    }

    /*
    206. 反转链表
    给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
    */
    public ListNode reverseList(ListNode head) {
        //空链表或只含一个结点的链表，不需要反转，直接返回该链表
        if(head == null || head.next == null){
            return head;
        }
        //反转含两个或者两个以上的结点的链表
        ListNode prev = null, cur = head, next = head.next;
        while(cur != null){
            next = cur.next;    //记录下一结点
            cur.next = prev;    //反转，将当前结点指向上一结点
            prev = cur;         //更新上一节点
            cur = next;         //更新当前结点
        }
        return prev;    //prev为反转后的链表
    }

    /*
    876. 链表的中间结点
    给你单链表的头结点 head ，请你找出并返回链表的中间结点。
    如果有两个中间结点，则返回第二个中间结点。
    */
    //双指针（快慢指针法）
    public ListNode middleNode(ListNode head) {
        ListNode fast = head, slow = head;
        //快指针走两步，慢指针走一步，循环结束，slow刚好为中间结点
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        //返回slow,即为中间结点
        return slow;
    }

    /*
    * 21. 合并两个有序链表
    *将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
    */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //创建一个傀儡结点作为新链表头结点，将小的结点进行尾插
        ListNode newHead = new ListNode(0), tail = newHead;
        while(list1 != null && list2 != null){
            //链表1节点的值小于链表2结点的值，将链表1的结点进行尾插到新链表
            if(list1.val < list2.val){
                tail.next = list1;  //将链表1的头结点进行尾插到新链表
                list1 = list1.next; //更新链表1的头结点
            }else{//链表1头节点的值大于等于链表2头结点的值，将链表2的结点进行尾插到新链表
                tail.next = list2;  //将链表2的头结点进行尾插到新链表
                list2 = list2.next; //更新链表2的头结点
            }
            tail = tail.next; //更新新链表的尾结点
        }
        //链表1剩余的结点尾接到新链表中
        if(list1 != null){
            tail.next = list1;
        }
        //链表2剩余的结点尾接到新链表中
        if(list2 != null){
            tail.next = list2;
        }

        return newHead.next;
    }

    /*
    * CM11 链表分割
    *现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在
    * 其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
    */
    public ListNode partition(ListNode pHead, int x) {
        // write code here
        //创建一个傀儡结点作为小于x的新链表头结点，并记录新链表的尾结点
        ListNode smallHead = new ListNode(0), smallTail = smallHead;
        //创建一个傀儡结点作为大于x的新链表头结点，并记录新链表的尾结点
        ListNode lagerHead = new ListNode(0), lagerTail = lagerHead;
        //遍历pHead链表，将结点的值与x比较，小于尾插到smallHead链表，大于尾插到lagerHead链表
        for(ListNode cur = pHead; cur != null; cur = cur.next){
            if(cur.val < x){
                smallTail.next = cur;
                smallTail = smallTail.next;
            }else{
                lagerTail.next = cur;
                lagerTail = lagerTail.next;
            }
        }
        //将大的链表链接到小的链表后面
        smallTail.next = lagerHead.next;
        //将大链表的尾结点的next置空
        lagerTail.next = null;

        return smallHead.next;
    }

    /*
    * OR36 链表的回文结构
    * 对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
    * 给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
    */
    public boolean chkPalindrome(ListNode A) {
        // write code here
        //空链表或者只有一个结点的链表是回文链表
        if(A == null || A.next == null){
            return true;
        }
        ListNode fast = A, slow = A;
        //快慢指针法找到中间结点
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        //头插法反转后半段链表
        ListNode cur = slow, next = null, newHead = null;
        while(cur != null){
            next = cur.next;
            cur.next = newHead;
            newHead = cur;
            cur = next;
        }
        //比较两个空链表的值
        ListNode head1 = A, head2 = newHead;
        while(head1 != null && head2 != null){
            //不相等返回false
            if(head1.val != head2.val){
                return false;
            }
            head1 = head1.next;
            head2 = head2.next;
        }
        //遍历完，都相等，返回true
        return true;
    }
    /*
    * 160. 相交链表
    * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单
    * 链表相交的起始节点。如果两个链表不存在相交节点，返回 null
    */
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = 0, lenB = 0;
        ListNode curA = headA, curB = headB;
        //求链表A的长度
        while(curA != null){
            lenA++;
            curA = curA.next;
        }
        //求链表B的长度
        while(curB != null){
            lenB++;
            curB = curB.next;
        }

        curA = headA;
        curB = headB;
        //求两条链表的长度差
        int len = (lenA > lenB ? lenA - lenB : lenB - lenA);
        //如果链表A的长度小于链表Bde长度，交换两条链表，保持链表A是长链表
        if(lenA < lenB){
            curA = headB;
            curB = headA;
        }
        //长链表先走长度差步
        while(len != 0){
            curA = curA.next;
            len--;
        }
        //同步遍历两条链表
        while(curA != null && curB != null){
            //两条链表遇到相交点，返回该结点
            if(curA == curB){
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        //遍历完，没有相交点，返回空
        return null;
    }
    /*
    * 141. 环形链表
    * 给你一个链表的头节点 head ，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，
    * 则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
    * 注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
    */
    public boolean hasCycle(ListNode head) {
        ListNode fast = head, slow = head;
        //快慢指针，快指针走两步，慢指针走一步
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            //快慢指针相遇，则有环，返回true
            if(fast == slow){
                return true;
            }
        }
        //无环，返回false
        return false;
    }

    /*
    * 142. 环形链表 II
    * 给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
    * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，
    * 评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，
    * 则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况
    */
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        boolean flag = false;
        //快慢指针，快指针走两步，慢指针走一步
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            //快慢指针相遇，则有环
            if(fast == slow){
                flag = true;
                break;
            }
        }
        //无环，返回null
        if(!flag){
            return null;
        }

        //有环，则从链表头和相遇点同步遍历链表，相遇则为环的入口
        ListNode cur1 = head, cur2 = slow;
        while(cur1 != null && cur2 != null){
            //相等，则为环的入口结点，跳出循环
            if(cur1 == cur2){
                break;
            }
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        //返回环的入口结点
        return cur1;
    }

    public static void test1(){
        ListNode head1 = null;
        ListNode head2 = null;
        for(int i = 0; i < 3; i++){
            ListNode node = new ListNode(i);
            node.next = head1;
            head1 = node;
        }
        head2 = head1;

        for(int i = 10; i < 13; i++){
            ListNode node = new ListNode(i);
            node.next = head1;
            head1 = node;
        }

        for(int i = 20; i < 25; i++){
            ListNode node = new ListNode(i);
            node.next = head2;
            head2 = node;
        }

        getIntersectionNode(head1, head2);

    }

    public static void main(String[] args) {
        test1();
        System.out.println();
    }

}
